1. Field of the Invention
This invention relates to electronic circuits for ensuring data integrity in data storage or data communication applications; in particular, this invention relates to electronic circuits for numerical computation in Galois fields useful in such applications.
2. Discussion of the Related Art
Error correction and error detection codes have been used extensively in data communication and data storage applications. In a data communication application, data is encoded prior to transmission, and decoded at the receiver. In a data storage application, data is encoded when stored in a storage device, e.g. a disk drive, and decoded when retrieved from the storage device. For the present discussion, it is unnecessary to distinguish between these applications. Hence, although the remainder of this description describes a data storage-retrieval system, the principles discussed herein are equally applicable to a data communication application.
In a typical application of error detection and correction codes, data symbols are stored in blocks. Each such block includes a selected number of special symbols, called check symbols. A symbol may consist of a single bit or multiple bits. The check symbols in each block represent redundant information concerning the data stored in the block. When decoding the blocked data, the check symbols are used to detect both the presence and the locations of errors and, in some instances, correct these errors. The theory and applications of error correction codes are described extensively in the literature. For example, the texts (i) "Error-Correcting Codes", Second Edition, by W. Wesley Peterson and E. J. Weldon, published by the MIT Press, Cambridge, Mass. (1972), and (ii) "Practical Error Correction Design for Engineers", revised second edition, by N. Glover and T. Dudley, Cirrus Logic, Colorado, publisher (1991), are well-known to those skilled in the art.
In a typical application of error correction codes, the input data is divided into fixed-length blocks ("code words"). Each code word consists of n symbols, of which a fixed number k are data symbols, and the remaining (n-k) symbols are check symbols. (For convenience, in this description, such a code is referred to as an (n, k) code). As mentioned above, the check symbols represent redundant information about the code word and can be used to provide error correction and detection capabilities. Conceptually, each data or check symbol of such a code word represents a coefficient of a polynomial of order (n-1). In the error correcting and detecting codes of this application, the check symbols are the coefficients of the remainder polynomial generated by dividing the order (n-1) polynomial by an order (n-k) "generator" polynomial over a Galois field. For a discussion of Galois fields, the reader is directed to .sctn.6.5 in the aforementioned text "Error-Correcting Codes" by W. Peterson and E. Weldon Jr. For an order (n-1) polynomial divided by an order (n-k) polynomial, the remainder polynomial is of order (n-k-1). Typically, in a data storage application, both the data symbols and the check symbols are stored.
During decoding, both data symbols and check symbols are read from the storage medium, and one or more "syndromes" are computed from the code word (i.e. the data and the check symbols) retrieved. A syndrome is a characteristic value computed from a remainder polynomial, which is obtained by dividing the code word retrieved by the generator polynomial. Ideally, if no error is encountered during the decoding process, all computed syndromes are zero. In some applications, e.g. in certain cyclic redundancy check schemes, a non-zero characteristic number results when no error is encountered. Without loss of generality, a syndrome of zero is assumed when no detectable error is encountered. A non-zero syndrome indicates that one or more errors exist in the code word. Depending on the nature of the generator polynomial and the type of error to be detected and corrected, the encountered error may or may not be correctable.
A well-known class of error correcting codes is the Reed-Solomon codes, which are characterized by the generator polynomial G(X), given by: EQU G(X)=(X+.alpha..sup.j) (X+.alpha..sup.j+1) (X+.alpha..sup.j+2) . . . (X+.alpha..sup.j+i-1) (X+.alpha..sup.j+i)
where .alpha. is a basis element of GF(2.sup.m) and, i and j are integers.
Because errors often occur in bursts, a technique, called "interleaving", is often used to spread the consecutive error bits or symbols into different "interleaves", which can each be corrected individually. Interleaving is achieved by creating a code word of length nw from w code words of length n. In one method for forming the new code word, the first w symbols of the new code word are provided by the first symbols of the w code words taken in a predetermined order. In the same predetermined order, the next symbol in each of the w code words is selected to be the next symbol in the new code word. This process is repeated until the last symbol of each of the w code words is selected in the predetermined order into the new code word. Another method to create a w-way interleaved code is to replace a generator polynomial G(X) of an (n, k) code by the generator polynomial G(X.sup.W). This technique is applicable, for example to the Reed-Solomon codes mentioned above. Using this new generator polynomial G(X.sup.W), the resulting (nw, kw) code has the error correcting and detecting capability of the original (n, k) code in each of the w interleaves so formed.
An error detection and correction system requires extensive calculation in finite Galois fields. In the prior art, such calculation is carried out by essentially unstructured customized random logic circuits consisting of logic gates and linear feedback shift registers. These logic circuits are complicated and relatively slow.